#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

class ShowStruct:
    INDENT = 4 * " "
    def __init__(self, tree_node, depth=0):
        self.tree_node = tree_node
        self.depth = depth

    def show(self):
        if self.tree_node:
            print(self.depth * self.INDENT, self.tree_node.value)


class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def set_value(self, other):
        if not other:
            self.value = 0
        else:
            self.value = other.value

    def show(self):
        print(self.value)


class WinnerTree:
    def __init__(self, nums):
        self.root = self.build(nums)

    def build(self, nums):
        if not nums:
            return None

        if len(nums) == 1:
            return TreeNode(nums[0])

        n = TreeNode()

        # 保证左边和右边相同, 或者左边数组比右边数组多一个
        # 因为树是左右平衡, 所以左右节点相差不要超过1
        # 注意: 这个生成的并不是"满树": 如果左右两颗数叶子节点数相同,
        # 那么生成形态也会相同, 这样如果左边不满, 右边也不满. 两边的最下层中间就会有空.
        m = (len(nums) + 1) // 2
        l_nums = nums[:m]
        r_nums = nums[m:]

        n.left,  n.right = self.build(l_nums), self.build(r_nums)

        if n.left is None:
            n.set_value(n.right)
        elif n.right is None:
            n.set_value(n.left)
        elif n.left.value > n.right.value:
            n.value = n.left.value
        else:
            n.value = n.right.value

        return n

    def build_rec(self, nums):
        pass

    def show(self):
        if self.root is None:
            return

        self.show_dfc(self.root)

    def show_dfc(self, node, depth=0):
        if node is None:
            return

        print(depth * "    ", node.value)
        self.show_dfc(node.left, depth+1)
        self.show_dfc(node.right, depth+1)

        # queue = [ ShowStruct(self.root) ]
        # idx = 0

        # while idx < len(queue):
        #     ss = queue[idx]
        #     n, depth = ss.tree_node, ss.depth
        #     print("put who's", n.value, idx)

        #     if n.left:
        #         queue.append( ShowStruct(n.left, depth + 1) )

        #     if n.right:
        #         queue.append( ShowStruct(n.right, depth + 1) )

        #     idx += 1

        # for ss in queue:
        #     ss.show()

def test():
    nums = [16, 32, 53, 1, 3, 8, 9, 5, 7, 6, 2]
    # nums = [1, 2, 3]
    w = WinnerTree(nums)
    w.show()
    r = w.root

    # print(r.value)
    # print(r.left.value)
    # print(r.left.left.value)
    # print(r.left.right.value)
    # print(r.right.value)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
